Josephus Problem

Posted: 2026-05-11 Tags: cs algorithm

contents

조세푸스 문제(Josephus Problem)는 수학과 컴퓨터 과학에서 아주 유명한 이론적 퍼즐입니다. 1세기 유대인 역사학자 플라비우스 조세푸스(Flavius Josephus)의 이름에서 유래했습니다. 전설에 따르면 조세푸스와 40명의 병사들은 로마군에 의해 동굴에 갇혔습니다. 그들은 포로로 잡히느니 차라리 자결하기로 결심하고 둥글게 둘러앉아 한 명만 남을 때까지 매 3번째 사람을 죽이기로 했습니다. 하지만 살고 싶었던 조세푸스는 로마군에게 항복하기 위해 자신이 마지막으로 남는 자리를 빠르게 계산해 냈습니다.

가장 널리 알려진 특수한 경우($k=2$)부터 시작해서 일반적인 경우로 확장하며 수학적 원리를 완벽하게 풀어보겠습니다.

파트 1: 특수한 경우 ($k = 2$)

이 문제는 매 두 번째 사람을 건너뛰며 제거할 때 수학적으로 가장 우아하게 풀립니다.

$n$명의 사람이 1번부터 $n$번까지 원형으로 서 있다고 가정해 봅시다. 처형은 1번부터 시작하여 1번이 2번을 죽이고, 3번이 4번을 죽이는 식으로 진행됩니다. 최후의 생존자 위치를 $J(n)$이라고 정의합시다.

이를 해결하기 위해 $n$이 짝수일 때와 홀수일 때 두 가지 경우로 나눕니다.

1. $n$이 짝수일 때 ($n = 2m$)

첫 번째 라운드에서 모든 짝수 번호(2, 4, 6, ..., $2m$)가 제거됩니다. 정확히 $m$명의 사람이 남게 되며, 이들은 모두 원래 홀수 번호(1, 3, 5, ..., $2m-1$)를 가지고 있습니다.

$2m-1$번이 $2m$번을 죽인 후, 다시 1번의 차례가 됩니다. 이제 $m$명으로 이루어진 더 작은 원이 생겼고 게임이 다시 시작됩니다.

새로운 위치를 원래 위치에 대응시켜 봅시다:

새로운 1번째 사람 = 원래 1번
새로운 2번째 사람 = 원래 3번
새로운 3번째 사람 = 원래 5번
새로운 $x$번째 사람 = 원래 $2x - 1$번

이로부터 첫 번째 점화식(Recurrence relation)을 얻을 수 있습니다:

$$J(2m) = 2J(m) - 1$$

2. $n$이 홀수일 때 ($n = 2m + 1$)

첫 번째 라운드에서 1번이 2번을, 3번이 4번을 죽이고, 결국 $2m-1$번이 $2m$번을 죽입니다. 이제 $2m+1$번의 차례입니다. 원형으로 둘러앉아 있기 때문에 $2m+1$번은 1번을 죽이게 됩니다.

이제 $m$명의 사람(3, 5, 7, ..., $2m+1$)이 남습니다. 다음 차례는 3번입니다.

새로운 위치를 원래 위치에 대응시켜 봅시다:

새로운 1번째 사람 = 원래 3번
새로운 2번째 사람 = 원래 5번
새로운 $x$번째 사람 = 원래 $2x + 1$번

이로부터 두 번째 점화식을 얻을 수 있습니다:

$$J(2m + 1) = 2J(m) + 1$$

파트 2: 닫힌 형태(Closed-Form) 해의 수학적 증명

위의 점화식을 사용하면 임의의 정수 $n$을 다음과 같은 형태로 표현할 수 있습니다:

$$n = 2^a + l$$

여기서 $2^a$는 $n$보다 작거나 같은 2의 거듭제곱 중 가장 큰 수이고, $l$은 나머지입니다 ($0 \le l < 2^a$).

정리: 최후의 생존자 위치는 다음과 같습니다:

$$J(n) = 2l + 1$$

강한 수학적 귀납법(Strong Induction)을 통한 증명:

기초 단계 (Base Case): $n=1$일 때, $2^a = 1$ (즉 $a=0$)이고 $l=0$입니다.

$J(1) = 2(0) + 1 = 1$. (혼자 남기 때문에 1이 맞습니다).

귀납 단계 (Inductive Step): $n-1$ 이하의 모든 값에 대해 위 정리가 성립한다고 가정합니다. 이제 $n$에 대해서도 성립함을 증명할 것입니다. 앞서 구한 짝수/홀수 점화식을 사용합니다.

경우 1: $n$이 짝수일 때 ($n = 2m$)

$n$이 짝수이므로 $n$과 $l$ 모두 짝수여야 합니다. $l = 2k$라고 합시다.

그러면 $m = n/2 = 2^{a-1} + k$가 됩니다.

귀납 가정에 의해: $J(m) = 2k + 1$.

짝수 점화식을 사용하면:

$$J(n) = J(2m) = 2J(m) - 1$$

$$J(n) = 2(2k + 1) - 1 = 4k + 1$$

$l = 2k$이므로, 이는 $2l + 1$로 정리됩니다. 공식이 성립합니다.

경우 2: $n$이 홀수일 때 ($n = 2m + 1$)

$n$이 홀수이므로 $l$도 홀수여야 합니다. $l = 2k + 1$이라고 합시다.

그러면 $m = (n-1)/2 = 2^{a-1} + k$가 됩니다.

귀납 가정에 의해: $J(m) = 2k + 1$.

홀수 점화식을 사용하면:

$$J(n) = J(2m + 1) = 2J(m) + 1$$

$$J(n) = 2(2k + 1) + 1 = 4k + 3$$

$l = 2k + 1$이므로, $4k + 3$은 $2(2k + 1) + 1$로 다시 쓸 수 있으며, 이는 정확히 $2l + 1$입니다. 공식이 성립합니다. $\blacksquare$

놀라운 이진법 트릭 (The Beautiful Binary Trick)

$n = 2^a + l$이기 때문에 닫힌 해 $2l + 1$은 이진법에서 매우 놀라운 트릭으로 변환됩니다. $n$을 이진수로 썼을 때, 최상위 비트(가장 왼쪽의 1)를 빼서 최하위 비트(가장 오른쪽)로 옮긴 후 십진수로 다시 변환하면 바로 생존자의 위치가 됩니다. 일종의 '1비트 원형 왼쪽 시프트(1-bit circular left shift)'입니다!

예시: $n = 41$

41은 이진수로 101001입니다.
첫 번째 1을 끝으로 옮깁니다: 010011.
010011은 십진수로 19입니다.

(수식 확인: $41 = 32 + 9$. $l = 9$. $J(41) = 2(9) + 1 = 19$).

파트 3: 일반적인 경우 (임의의 $k$)

매 $k$번째 사람을 죽이는 것으로 건너뛰는 숫자를 바꾸면, 멋진 이진법 트릭은 사라지고 동적 계획법(Dynamic Programming)과 모듈러 연산(Modular Arithmetic)에 의존해야 합니다.

0-based 인덱스를 사용해 보겠습니다 (사람들에게 0번부터 $n-1$번까지 번호를 매김). $n$명의 사람과 건너뛰는 간격이 $k$일 때, 생존자의 위치를 $f(n, k)$라고 합시다.

기초 단계: 1명만 있다면, 그 사람은 인덱스 0에서 생존합니다.

$$f(1, k) = 0$$

점화식: 인덱스 $(k-1) \mod n$에서 첫 번째 사람이 죽고 나면, $n-1$명의 원이 남습니다. 다음 라운드는 인덱스 $k \mod n$에서 시작됩니다.

이 작아진 새로운 원은 마치 $f(n-1, k)$ 게임처럼 동작하지만, 모든 인덱스가 $k$만큼 앞으로 밀려나(shift) 있습니다. 따라서 원본 $n$명의 원에서 생존자 위치를 찾으려면, $n-1$명 원에서의 생존자 위치를 구한 후 $k$만큼 더하고, 모듈러 $n$을 사용해 원형을 한 바퀴 돌려주면 됩니다.

$$f(n, k) = (f(n-1, k) + k) \mod n$$

표준적인 1-based 인덱스(1번부터 시작) 정답을 얻으려면, 마지막에 구한 $f(n, k)$에 1을 더해주기만 하면 됩니다.

references